{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Groups With Increasing Length"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxIncreasingGroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #长度递增组的最大数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、长度为 <code>n</code> 的数组 <code>usageLimits</code> 。</p>\n",
    "\n",
    "<p>你的任务是使用从 <code>0</code> 到 <code>n - 1</code> 的数字创建若干组，并确保每个数字 <code>i</code> 在 <strong>所有组</strong> 中使用的次数总共不超过 <code>usageLimits[i]</code> 次。此外，还必须满足以下条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个组必须由 <strong>不同</strong> 的数字组成，也就是说，单个组内不能存在重复的数字。</li>\n",
    "\t<li>每个组（除了第一个）的长度必须 <strong>严格大于</strong> 前一个组。</li>\n",
    "</ul>\n",
    "\n",
    "<p>在满足所有条件的情况下，以整数形式返回可以创建的最大组数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<code><strong>输入：</strong>usageLimits</code> = [1,2,5]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>在这个示例中，我们可以使用 0 至多一次，使用 1 至多 2 次，使用 2 至多 5 次。\n",
    "一种既能满足所有条件，又能创建最多组的方式是： \n",
    "组 1 包含数字 [2] 。\n",
    "组 2 包含数字 [1,2] 。\n",
    "组 3 包含数字 [0,1,2] 。 \n",
    "可以证明能够创建的最大组数是 3 。 \n",
    "所以，输出是 3 。 </pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<code><strong>输入：</strong></code><code>usageLimits</code> = [2,1,2]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>在这个示例中，我们可以使用 0 至多 2 次，使用 1 至多 1 次，使用 2 至多 2 次。\n",
    "一种既能满足所有条件，又能创建最多组的方式是： \n",
    "组 1 包含数字 [0] 。 \n",
    "组 2 包含数字 [1,2] 。\n",
    "可以证明能够创建的最大组数是 2 。 \n",
    "所以，输出是 2 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<code><strong>输入：</strong></code><code>usageLimits</code> = [1,1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>在这个示例中，我们可以使用 0 和 1 至多 1 次。 \n",
    "一种既能满足所有条件，又能创建最多组的方式是：\n",
    "组 1 包含数字 [0] 。\n",
    "可以证明能够创建的最大组数是 1 。 \n",
    "所以，输出是 1 。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= usageLimits.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= usageLimits[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-groups-with-increasing-length](https://leetcode.cn/problems/maximum-number-of-groups-with-increasing-length/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-groups-with-increasing-length](https://leetcode.cn/problems/maximum-number-of-groups-with-increasing-length/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,5]', '[2,1,2]', '[1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        n = len(usageLimits)\n",
    "        x = 1 \n",
    "        for i in range(n):\n",
    "            if usageLimits[i] >= x:\n",
    "                usageLimits[i] -= x \n",
    "                x += 1 \n",
    "            if i < n - 1:\n",
    "                usageLimits[i + 1] += usageLimits[i]\n",
    "        return x - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        n = len(usageLimits)\n",
    "        x = 1 \n",
    "        for i in range(n):\n",
    "            if x <= usageLimits[i]:\n",
    "                usageLimits[i] -= x \n",
    "                x += 1 \n",
    "            if i < n - 1:\n",
    "                usageLimits[i + 1] += usageLimits[i] \n",
    "        return x - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        x = 1 \n",
    "        n = len(usageLimits)\n",
    "        for i in range(n):\n",
    "            if usageLimits[i] >= x:\n",
    "                usageLimits[i] -= x \n",
    "                x += 1\n",
    "            if i < n - 1:\n",
    "                usageLimits[i + 1] += usageLimits[i]\n",
    "        return x - 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        usageLimits.reverse()\n",
    "        def test(T):\n",
    "            k=0\n",
    "            for i in range(T):\n",
    "                if usageLimits[i]>T-i and k<0:\n",
    "                    k+=usageLimits[i]+i-T\n",
    "                    if k>0:\n",
    "                        k=0\n",
    "                elif usageLimits[i]<T-i:\n",
    "                    k+=usageLimits[i]+i-T\n",
    "            k+=sum(usageLimits[T:])\n",
    "            if k>=0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        M=len(usageLimits)+1\n",
    "        m=0\n",
    "        while M-m>1:\n",
    "            mid=(M+m)//2\n",
    "            if test(mid):\n",
    "                m=mid\n",
    "            else:\n",
    "                M=mid\n",
    "        return m\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        take = []\n",
    "        backup = []\n",
    "        N = 0\n",
    "        while True:\n",
    "            if not usageLimits and not backup:\n",
    "                break\n",
    "            if not backup or (usageLimits and backup[-1][0] == usageLimits[-1]):\n",
    "                nextNumber = usageLimits.pop()\n",
    "                c = 1\n",
    "                while usageLimits and usageLimits[-1] == nextNumber:\n",
    "                    usageLimits.pop()\n",
    "                    c += 1\n",
    "                if backup and backup[-1][0] == nextNumber:\n",
    "                    backup[-1] = (nextNumber, backup[-1][1] + c)\n",
    "                else:\n",
    "                    backup.append((nextNumber, c))\n",
    "            #print(\"N=\", N, \"backup=\", backup, \"take=\", take)\n",
    "            target = 1\n",
    "            if take and take[-1][0] - N < backup[-1][0]:\n",
    "                assert take[-1][0] - N == backup[-1][0] - 1\n",
    "                target += take[-1][1]\n",
    "                if len(backup) == 1:\n",
    "                    v, c = take.pop()\n",
    "                    backup.insert(0, (v - N, c))\n",
    "                else:\n",
    "                    backup[0] = (backup[0][0], backup[0][1] + take.pop()[1])\n",
    "            while target:\n",
    "                v, c = backup.pop()\n",
    "                if target >= c:\n",
    "                    target -= c\n",
    "                else:\n",
    "                    backup.append((v, c - target))\n",
    "                    c = target\n",
    "                    target = 0\n",
    "                v += N\n",
    "                if take and take[-1][0] == v:\n",
    "                    take[-1] = (v, take[-1][1] + c)\n",
    "                else:\n",
    "                    take.append((v, c))\n",
    "            #print(\"take=\", take)\n",
    "            if take[-1][0] <= N:\n",
    "                break\n",
    "            N += 1\n",
    "        return N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        ul = sorted(usageLimits)\n",
    "        remain = 0 # 前面数组多余的数量\n",
    "        require = 1 # 最小目标序列需要的长度，从1~n\n",
    "        for num in ul:\n",
    "            remain += num\n",
    "            if remain >= require: # 如果当前位置积累的数量达到了目标序列的要求\n",
    "                remain -= require \n",
    "                require += 1 \n",
    "        return require - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        ul = sorted(usageLimits)\n",
    "        more = 0\n",
    "        require = 1\n",
    "        for i in ul:\n",
    "            more += i\n",
    "            if more >= require:\n",
    "                more -= require\n",
    "                require += 1\n",
    "        return require - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        ans = temp = 0\n",
    "        for a in sorted(usageLimits):\n",
    "            temp += a\n",
    "            # 检查能否构造出(ans + 1)组\n",
    "            if temp >= (ans + 1) * (ans + 2) // 2:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        ul = sorted(usageLimits)\n",
    "        remain = 0 # 前面数组多余的数量\n",
    "        require = 1 # 最小目标序列需要的长度，从1~n\n",
    "        for num in ul:\n",
    "            remain += num\n",
    "            if remain >= require: # 如果当前位置积累的数量达到了目标序列的要求\n",
    "                remain -= require \n",
    "                require += 1 \n",
    "        return require - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits=sorted(usageLimits,reverse=True)\n",
    "        n=len(usageLimits)\n",
    "        ans=0\n",
    "        left=1\n",
    "        right=n\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if left==mid:\n",
    "                mid+=1\n",
    "            moreuse=0\n",
    "            needuse=0\n",
    "            for i in range(mid):\n",
    "                if mid-i>=usageLimits[i]:\n",
    "                    needuse=needuse+mid-i-usageLimits[i]\n",
    "                elif needuse>0:\n",
    "                    moreuse=usageLimits[i]+i-mid\n",
    "                    if needuse<=moreuse:\n",
    "                        moreuse=0\n",
    "                        needuse=0\n",
    "                    else:\n",
    "                        needuse=needuse-moreuse\n",
    "                        moreuse=0\n",
    "            for i in range(mid,n):\n",
    "                needuse-=usageLimits[i]\n",
    "            if needuse>0:\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid\n",
    "        return left\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        ul = sorted(usageLimits)\n",
    "        remain = 0 # 前面数组多余的数量\n",
    "        require = 1 # 最小目标序列需要的长度，从1~n\n",
    "        for num in ul:\n",
    "            remain += num\n",
    "            if remain >= require: # 如果当前位置积累的数量达到了目标序列的要求\n",
    "                remain -= require \n",
    "                require += 1 \n",
    "        return require - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        n = len(usageLimits)\n",
    "        usageLimits.sort()\n",
    "        cache = 0\n",
    "        res = 0\n",
    "        for x in usageLimits:\n",
    "            cache+=x\n",
    "            if cache>=res+1:\n",
    "                cache-=res+1\n",
    "                res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort(reverse=True)\n",
    "        def check(n):\n",
    "            gap = 0\n",
    "            for u in usageLimits:\n",
    "                if n==0 and gap>=0:\n",
    "                    break\n",
    "                gap = u - n + gap\n",
    "                if gap > 0:\n",
    "                    gap = 0\n",
    "                if n > 0:\n",
    "                    n -= 1\n",
    "            if gap < 0:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "\n",
    "\n",
    "      \n",
    "\n",
    "\n",
    "\n",
    "        left = 0\n",
    "        right = len(usageLimits) + 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid \n",
    "\n",
    "        return left - 1\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, a: List[int]) -> int:\n",
    "        a.sort()\n",
    "        s=ans=0\n",
    "        for v in a:\n",
    "            s+=v\n",
    "            if s>=(ans+1)*(ans+2)//2:\n",
    "                ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort(reverse = True)\n",
    "\n",
    "        def check(n : int) -> bool:\n",
    "            gap = 0\n",
    "            for x in usageLimits:\n",
    "                gap = min(gap + x - n, 0)\n",
    "                if n > 0:\n",
    "                    n -= 1\n",
    "            return gap >= 0\n",
    "        \n",
    "        lower, upper = 0, len(usageLimits)\n",
    "        while lower < upper:\n",
    "            mid = int((lower + upper + 1) / 2)\n",
    "            lower, upper = (mid, upper) if check(mid) else (lower, mid - 1)\n",
    "        \n",
    "        return lower\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        ul = sorted(usageLimits)\n",
    "        remain = 0 # 前面数组多余的数量\n",
    "        require = 1 # 最小目标序列需要的长度，从1~n\n",
    "        for num in ul:\n",
    "            remain += num\n",
    "            if remain >= require: # 如果当前位置积累的数量达到了目标序列的要求\n",
    "                remain -= require \n",
    "                require += 1 \n",
    "        return require - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        ul = sorted(usageLimits)\n",
    "        remain = 0\n",
    "        require = 1\n",
    "        for num in ul:\n",
    "            remain += num\n",
    "            if remain >= require:\n",
    "                remain -= require\n",
    "                require += 1\n",
    "        return require - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        i = cur = left = 0\n",
    "        for i in range(n):\n",
    "            left += arr[i]\n",
    "            if left >= cur + 1:\n",
    "                cur += 1\n",
    "                left -= cur\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort(reverse=True)\n",
    "\n",
    "        def check(n):\n",
    "            gap = 0\n",
    "            i = n\n",
    "            for x in usageLimits:\n",
    "                gap = min(x - i + gap, 0)\n",
    "\n",
    "                if i > 0:\n",
    "                    i -= 1\n",
    "\n",
    "            return 0 if gap >= 0 else 1\n",
    "\n",
    "        return bisect_left(range(len(usageLimits) + 1), 1, key=check) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        left, right = 1, len(usageLimits)\n",
    "        if self.can_create(usageLimits, right):\n",
    "            return right\n",
    "        while right - left > 1:\n",
    "            mid = (left + right) // 2\n",
    "            if self.can_create(usageLimits, mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def can_create(self, usage_limits: List[int], num_groups: int) -> bool:\n",
    "        gap, group_size = 0, num_groups\n",
    "        for i in range(len(usage_limits) - 1, -1, -1):\n",
    "            if usage_limits[i] >= group_size:\n",
    "                gap = max(0, gap - (usage_limits[i] - group_size))\n",
    "            else:\n",
    "                gap += group_size - usage_limits[i]\n",
    "            group_size = max(0, group_size - 1)\n",
    "        return gap == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        n = len(usageLimits)\n",
    "\n",
    "        cache = 0\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            x = usageLimits[i]\n",
    "\n",
    "            if x + cache >= ret + 1:\n",
    "                cache = x + cache - ret - 1\n",
    "                ret += 1\n",
    "            else:\n",
    "                cache += x\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        \n",
    "        def check(usageLimits, n):\n",
    "            gap = 0\n",
    "            for item in usageLimits:\n",
    "                gap = min(gap - n + item, 0)\n",
    "                if n > 0:\n",
    "                    n -= 1\n",
    "            return gap >= 0\n",
    "        \n",
    "        \n",
    "        usageLimits.sort(reverse = True)\n",
    "        l, h = 0, len(usageLimits)\n",
    "        while l < h:\n",
    "            m = (l+h+1)//2\n",
    "            if check(usageLimits, m):\n",
    "                l, h = m, h\n",
    "            else:\n",
    "                l, h = l, m-1\n",
    "        return h "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, a: List[int]) -> int:\n",
    "        a.sort()\n",
    "        s=group=0\n",
    "        for v in a:\n",
    "            s+=v\n",
    "            # if成立时，会生成新的一列\n",
    "            if s>=group+1:\n",
    "                group+=1\n",
    "                s-=group\n",
    "        return group\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort(reverse = True)\n",
    "\n",
    "        def check(n : int) -> bool:\n",
    "            gap = 0\n",
    "            for x in usageLimits:\n",
    "                gap = min(gap + x - n, 0)\n",
    "                if n > 0:\n",
    "                    n -= 1\n",
    "            return gap >= 0\n",
    "        \n",
    "        lower, upper = 0, len(usageLimits)\n",
    "        while lower < upper:\n",
    "            mid = int((lower + upper + 1) / 2)\n",
    "            lower, upper = (mid, upper) if check(mid) else (lower, mid - 1)\n",
    "        \n",
    "        return lower"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        left, right = 1, len(usageLimits)\n",
    "        if self.can_create(usageLimits, right):\n",
    "            return right\n",
    "        while right - left > 1:\n",
    "            mid = (left + right) // 2\n",
    "            if self.can_create(usageLimits, mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def can_create(self, usage_limits: List[int], num_groups: int) -> bool:\n",
    "        gap, group_size = 0, num_groups\n",
    "        for i in range(len(usage_limits) - 1, -1, -1):\n",
    "            if usage_limits[i] >= group_size:\n",
    "                gap = max(0, gap - (usage_limits[i] - group_size))\n",
    "            else:\n",
    "                gap += group_size - usage_limits[i]\n",
    "            group_size = max(0, group_size - 1)\n",
    "            if group_size == 0 and gap == 0:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort(reverse=True)\n",
    "        \n",
    "        def check(n):\n",
    "            rest = 0\n",
    "            for i in usageLimits:\n",
    "                rest += max(n - i, -rest)\n",
    "                n = max(0, n - 1)\n",
    "                if n == rest == 0: break\n",
    "                \n",
    "            return bool(n) or bool(rest)\n",
    "        \n",
    "        return bisect_left(range(len(usageLimits) + 1), True, key=check) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        # h = []\n",
    "        # h = [[-x, i] for i,x in enumerate(usageLimits)]\n",
    "        # heapify(h)\n",
    "        # times = 1\n",
    "        # while len(h) >= times:\n",
    "        #     asc = []\n",
    "        #     for k in range(times):\n",
    "        #         a, b = heappop(h)\n",
    "        #         asc += [[a, b]]\n",
    "        #     for j, k in asc:\n",
    "        #         if -j > 1:\n",
    "        #             heappush(h, [1+j, k])\n",
    "        #     print(asc)\n",
    "        #     times += 1\n",
    "        # return times - 1\n",
    "        # 不必带上下标 我们只需要塞数据 只要够塞 即不会有重复数组\n",
    "        # 使用差分数组 只需要判断最小的usageLimits[i]是否大于0\n",
    "        usageLimits.sort()\n",
    "        n = len(usageLimits)\n",
    "        ans = val = 0\n",
    "        for x in usageLimits:\n",
    "            val += x\n",
    "            if (ans+1)*(ans+2)//2 <= val:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        n = len(usageLimits)\n",
    "        usageLimits.sort()\n",
    "\n",
    "        def check(target: int) -> bool:\n",
    "            total = 0\n",
    "            for idx,num in enumerate(usageLimits):\n",
    "                if idx < target: total += num\n",
    "                else: total += num - (idx - target + 1)\n",
    "                if total < 0: return False\n",
    "            return True\n",
    "\n",
    "        left, right = 0, n\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if check(mid): right = mid\n",
    "            else: left = mid + 1\n",
    "\n",
    "        return n - right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort() \n",
    "        ans = s = 0\n",
    "        for v in usageLimits:\n",
    "            s += v\n",
    "            if s >= (ans+2) * (ans+1) // 2:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        ans = s = 0\n",
    "        for v in usageLimits:\n",
    "            s += v\n",
    "            # 看看能否构造出 ans+1 组\n",
    "            if s >= (ans+2) * (ans+1) // 2:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        ans = s = 0\n",
    "        for v in usageLimits:\n",
    "            s += v\n",
    "            if s >= (ans + 2) * (ans + 1) // 2:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        avl = 0\r\n",
    "        usageLimits.sort()\r\n",
    "        for ul in usageLimits:\r\n",
    "            avl += ul\r\n",
    "            if avl > res:\r\n",
    "                res += 1\r\n",
    "                avl -= res\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, u: List[int]) -> int:\n",
    "        u.sort()\n",
    "        limit = 1\n",
    "        remaining = 0\n",
    "        for p in u:\n",
    "            remaining += p\n",
    "            if remaining >= limit:\n",
    "                remaining -= limit\n",
    "                limit += 1\n",
    "        return limit - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        ans=s=0\n",
    "        for x in usageLimits:\n",
    "            s+=x\n",
    "            if s>=(ans+2)*(ans+1)//2:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits):\n",
    "        usageLimits.sort()\n",
    "        available = 0\n",
    "        group = 0\n",
    "        for limit in usageLimits:\n",
    "            available += limit\n",
    "            if available > group:\n",
    "                group += 1\n",
    "                available -= group\n",
    "        return group\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort(reverse = True)\n",
    "\n",
    "        def check(n: int) -> bool:\n",
    "            gap = 0\n",
    "            for x in usageLimits:\n",
    "                gap = min(gap + x - n, 0)\n",
    "                if n > 0:\n",
    "                    n -= 1\n",
    "            return gap >= 0\n",
    "        \n",
    "        lower, upper = 0, len(usageLimits)\n",
    "        while lower < upper:\n",
    "            mid = int((lower + upper + 1) / 2)\n",
    "            lower, upper = (mid, upper) if check(mid) else (lower, mid - 1)\n",
    "        \n",
    "        return lower\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort(reverse = True)\n",
    "\n",
    "        def check(n : int) -> bool:\n",
    "            gap = 0\n",
    "            for x in usageLimits:\n",
    "                gap = min(gap + x - n, 0)\n",
    "                if n > 0:\n",
    "                    n -= 1\n",
    "            return gap >= 0\n",
    "        \n",
    "        lower, upper = 0, len(usageLimits)\n",
    "        while lower < upper:\n",
    "            mid = int((lower + upper + 1) / 2)\n",
    "            lower, upper = (mid, upper) if check(mid) else (lower, mid - 1)\n",
    "        \n",
    "        return lower\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        require = 1\n",
    "        remain = 0\n",
    "        for usage in usageLimits:\n",
    "            remain += usage\n",
    "            if remain >= require:\n",
    "                remain -= require\n",
    "                require += 1\n",
    "        return require - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort()\n",
    "        ans = s = 0\n",
    "        for v in usageLimits:\n",
    "            s += v\n",
    "            # 看看能否构造出 ans+1 组\n",
    "            if s >= (ans+2) * (ans+1) // 2:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "        usageLimits.sort(reverse=True)\n",
    "        def check(n):\n",
    "            gap = 0\n",
    "            for u in usageLimits:\n",
    "                \n",
    "                gap = u - n + gap\n",
    "                if gap > 0:\n",
    "                    gap = 0\n",
    "                if n > 0:\n",
    "                    n -= 1\n",
    "            if gap < 0:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "\n",
    "\n",
    "      \n",
    "\n",
    "\n",
    "\n",
    "        left = 0\n",
    "        right = len(usageLimits) + 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid \n",
    "\n",
    "        return left - 1\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingGroups(self, usageLimits: List[int]) -> int:\n",
    "\n",
    "        usageLimits.sort(reverse=True)\n",
    "        n = len(usageLimits)\n",
    "        l, r = 1, n + 1\n",
    "\n",
    "        def help(k):\n",
    "            gap = 0\n",
    "            for x in usageLimits:\n",
    "                gap = min(gap + x - k, 0)\n",
    "                if k > 0:\n",
    "                    k -= 1\n",
    "            return gap >= 0\n",
    "\n",
    "\n",
    "        while l < r:\n",
    "\n",
    "            mid = (l + r) // 2\n",
    "\n",
    "            if help(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l - 1\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
